home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 2 / LSD and 17bit Compendium Deluxe - Volume II.iso / a / prog / asmsrc / thesource-7.lha / Source / Articles / Stereoscopic / SegaGlasses.lha / SegaGlasses / dgif.c < prev    next >
C/C++ Source or Header  |  1992-07-16  |  13KB  |  370 lines
  1. /* DECODE.C - An LZW decoder for GIF
  2.  * Copyright (C) 1987, by Steven A. Bennett
  3.  *
  4.  * Permission is given by the author to freely redistribute and include
  5.  * this code in any program as long as this credit is given where due.
  6.  *
  7.  * In accordance with the above, I want to credit Steve Wilhite who wrote
  8.  * the code which this is heavily inspired by...
  9.  *
  10.  * GIF and 'Graphics Interchange Format' are trademarks (tm) of
  11.  * Compuserve, Incorporated, an H&R Block Company.
  12.  *
  13.  * Release Notes: This file contains a decoder routine for GIF images
  14.  * which is similar, structurally, to the original routine by Steve Wilhite.
  15.  * It is, however, somewhat noticably faster in most cases.
  16.  *
  17.  */
  18.  
  19. #include <alloc.h>
  20. #include "dgif.h"
  21.  
  22. /* extern int get_byte()
  23.  *
  24.  *   - This external (machine specific) function is expected to return
  25.  * either the next byte from the GIF file, or a negative number, as
  26.  * defined in ERRS.H.
  27.  */
  28. extern int get_byte();
  29.  
  30. /* extern int out_line(pixels, linelen)
  31.  *     unsigned char pixels[];
  32.  *     int linelen;
  33.  *
  34.  *   - This function takes a full line of pixels (one byte per pixel) and
  35.  * displays them (or does whatever your program wants with them...).  It
  36.  * should return zero, or negative if an error or some other event occurs
  37.  * which would require aborting the decode process...  Note that the length
  38.  * passed will almost always be equal to the line length passed to the
  39.  * decoder function, with the sole exception occurring when an ending code
  40.  * occurs in an odd place in the GIF file...  In any case, linelen will be
  41.  * equal to the number of pixels passed...
  42.  */
  43. extern int out_line();
  44.  
  45. /* extern int bad_code_count;
  46.  *
  47.  * This value is the only other global required by the using program, and
  48.  * is incremented each time an out of range code is read by the decoder.
  49.  * When this value is non-zero after a decode, your GIF file is probably
  50.  * corrupt in some way...
  51.  */
  52. extern int bad_code_count;
  53.  
  54. #define MAX_CODES   4095
  55.  
  56. /* Static variables */
  57. static short curr_size;                   /* The current code size */
  58. static short clear;                       /* Value for a clear code */
  59. static short ending;                      /* Value for a ending code */
  60. static short newcodes;                    /* First available code */
  61. static short top_slot;                    /* Highest code for current size */
  62. static short slot;                        /* Last read code */
  63.  
  64. /* The following static variables are used
  65.  * for seperating out codes
  66.  */
  67. static short         navail_bytes = 0;    /* # bytes left in block */
  68. static short         nbits_left = 0;      /* # bits left in current byte */
  69. static unsigned char b1;                  /* Current byte */
  70. static unsigned char byte_buff[257];      /* Current block */
  71. static unsigned char *pbytes;             /* Pointer to next byte in block */
  72.  
  73. static long code_mask[13] = { 0,
  74.                               0x0001, 0x0003,
  75.                               0x0007, 0x000F,
  76.                               0x001F, 0x003F,
  77.                               0x007F, 0x00FF,
  78.                               0x01FF, 0x03FF,
  79.                               0x07FF, 0x0FFF
  80.                             };
  81.  
  82.  
  83. /* This function initializes the decoder for reading a new image.
  84.  */
  85. static short init_exp(size)
  86.                       short size;
  87. {
  88.     curr_size = size + 1;
  89.     top_slot = 1 << curr_size;
  90.     clear = 1 << size;
  91.     ending = clear + 1;
  92.     slot = newcodes = ending + 1;
  93.     navail_bytes = nbits_left = 0;
  94.     return(0);
  95. }
  96.  
  97. /* get_next_code()
  98.  * - gets the next code from the GIF file.  Returns the code, or else
  99.  * a negative number in case of file errors...
  100.  */
  101. static short get_next_code()
  102. {
  103.     short i, x;
  104.     unsigned long ret;
  105.  
  106.     if (nbits_left == 0)
  107.     {
  108.         if (navail_bytes <= 0)
  109.         {
  110.  
  111.             /* Out of bytes in current block, so read next block */
  112.             pbytes = byte_buff;
  113.             if ((navail_bytes = get_byte()) < 0)
  114.                 return(navail_bytes);
  115.             else if (navail_bytes)
  116.             {
  117.                 for (i = 0; i < navail_bytes; ++i)
  118.                 {
  119.                     if ((x = get_byte()) < 0)
  120.                         return(x);
  121.                     byte_buff[i] = x;
  122.                 }
  123.             }
  124.         }
  125.         b1 = *pbytes++;
  126.         nbits_left = 8;
  127.         --navail_bytes;
  128.     }
  129.  
  130.     ret = b1 >> (8 - nbits_left);
  131.     while (curr_size > nbits_left)
  132.     {
  133.         if (navail_bytes <= 0)
  134.         {
  135.             /* Out of bytes in current block, so read next block */
  136.  
  137.             pbytes = byte_buff;
  138.             if ((navail_bytes = get_byte()) < 0)
  139.                 return(navail_bytes);
  140.             else if (navail_bytes)
  141.             {
  142.                 for (i = 0; i < navail_bytes; ++i)
  143.                 {
  144.                     if ((x = get_byte()) < 0)
  145.                         return(x);
  146.                     byte_buff[i] = x;
  147.                 }
  148.             }
  149.         }
  150.         b1 = *pbytes++;
  151.         ret |= b1 << nbits_left;
  152.         nbits_left += 8;
  153.         --navail_bytes;
  154.     }
  155.     nbits_left -= curr_size;
  156.     ret &= code_mask[curr_size];
  157.         return((short)(ret));
  158. }
  159.  
  160.  
  161. /* The reason we have these seperated like this instead of using
  162.  * a structure like the original Wilhite code did, is because this
  163.  * stuff generally produces significantly faster code when compiled...
  164.  * This code is full of similar speedups...  (For a good book on writing
  165.  * C for speed or for space optomisation, see Efficient C by Tom Plum,
  166.  * published by Plum-Hall Associates...)
  167.  */
  168. static unsigned char stack[MAX_CODES + 1];            /* Stack for storing pixels */
  169. static unsigned char suffix[MAX_CODES + 1];           /* Suffix table */
  170. static unsigned short prefix[MAX_CODES + 1];           /* Prefix linked list */
  171.  
  172. /* short decoder(linewidth)
  173.  *    short linewidth;               * Pixels per line of image *
  174.  *
  175.  * - This function decodes an LZW image, according to the method used
  176.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  177.  * will generate a call to out_line(), which is a user specific function
  178.  * to display a line of pixels.  The function gets it's codes from
  179.  * get_next_code() which is responsible for reading blocks of data and
  180.  * seperating them into the proper size codes.  Finally, get_byte() is
  181.  * the global routine to read the next byte from the GIF file.
  182.  *
  183.  * It is generally a good idea to have linewidth correspond to the actual
  184.  * width of a line (as specified in the Image header) to make your own
  185.  * code a bit simpler, but it isn't absolutely necessary.
  186.  *
  187.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  188.  *
  189.  */
  190.  
  191. short decoder(linewidth)
  192.               short linewidth;
  193. {
  194.     register unsigned char *sp, *bufptr;
  195.     unsigned char *buf;
  196.     register short code, fc, oc, bufcnt;
  197.     short c, size, ret;
  198.  
  199.     /* Initialize for decoding a new image... */
  200.  
  201.     if ((size = get_byte()) < 0)
  202.         return(size);
  203.     if (size < 2 || 9 < size)
  204.         return(BAD_CODE_SIZE);
  205.     init_exp(size);
  206.  
  207.     /* Initialize in case they forgot to put in a clear code.
  208.      * (This shouldn't happen, but we'll try and decode it anyway...)
  209.      */
  210.     oc = fc = 0;
  211.  
  212.     /* Allocate space for the decode buffer
  213.      */
  214.     if ((buf = (unsigned char *)malloc(linewidth + 1)) == NULL)
  215.          return(OUT_OF_MEMORY);
  216.  
  217.     /* Set up the stack pointer and decode buffer pointer
  218.      */
  219.     sp = stack;
  220.     bufptr = buf;
  221.     bufcnt = linewidth;
  222.  
  223.     /* This is the main loop.  For each code we get we pass through the
  224.      * linked list of prefix codes, pushing the corresponding "character" for
  225.      * each code onto the stack.  When the list reaches a single "character"
  226.      * we push that on the stack too, and then start unstacking each
  227.      * character for output in the correct order.  Special handling is
  228.      * included for the clear code, and the whole thing ends when we get
  229.      * an ending code.
  230.      */
  231.     while ((c = get_next_code()) != ending)
  232.     {
  233.  
  234.         /* If we had a file error, return without completing the decode
  235.          */
  236.         if (c < 0)
  237.         {
  238.             free(buf);
  239.             return(0);
  240.         }
  241.  
  242.         /* If the code is a clear code, reinitialize all necessary items.
  243.          */
  244.         if (c == clear)
  245.         {
  246.             curr_size = size + 1;
  247.             slot = newcodes;
  248.             top_slot = 1 << curr_size;
  249.  
  250.             /* Continue reading codes until we get a non-clear code
  251.              * (Another unlikely, but possible case...)
  252.              */
  253.             while ((c = get_next_code()) == clear);
  254.  
  255.             /* If we get an ending code immediately after a clear code
  256.              * (Yet another unlikely case), then break out of the loop.
  257.              */
  258.             if (c == ending)
  259.                 break;
  260.  
  261.             /* Finally, if the code is beyond the range of already set codes,
  262.              * (This one had better NOT happen...  I have no idea what will
  263.              * result from this, but I doubt it will look good...) then set it
  264.              * to color zero.
  265.              */
  266.             if (c >= slot)
  267.                 c = 0;
  268.  
  269.             oc = fc = c;
  270.  
  271.             /* And let us not forget to put the char into the buffer... And
  272.              * if, on the off chance, we were exactly one pixel from the end
  273.              * of the line, we have to send the buffer to the out_line()
  274.              * routine...
  275.              */
  276.             *bufptr++ = c;
  277.             if (--bufcnt == 0)
  278.             {
  279.                 if ((ret = out_line(buf, linewidth)) < 0)
  280.                 {
  281.                     free(buf);
  282.                     return(ret);
  283.                 }
  284.                 bufptr = buf;
  285.                 bufcnt = linewidth;
  286.             }
  287.         }
  288.         else
  289.         {
  290.  
  291.             /* In this case, it's not a clear code or an ending code, so
  292.              * it must be a code code...  So we can now decode the code into
  293.              * a stack of character codes. (Clear as mud, right?)
  294.              */
  295.             code = c;
  296.  
  297.             /* Here we go again with one of those off chances...  If, on the
  298.              * off chance, the code we got is beyond the range of those already
  299.              * set up (Another thing which had better NOT happen...) we trick
  300.              * the decoder into thinking it actually got the last code read.
  301.              * (Hmmn... I'm not sure why this works...  But it does...)
  302.              */
  303.             if (code >= slot)
  304.             {
  305.                 if (code > slot)
  306.                     ++bad_code_count;
  307.                 code = oc;
  308.                 *sp++ = fc;
  309.             }
  310.  
  311.             /* Here we scan back along the linked list of prefixes, pushing
  312.              * helpless characters (ie. suffixes) onto the stack as we do so.
  313.              */
  314.             while (code >= newcodes)
  315.             {
  316.                 *sp++ = suffix[code];
  317.                 code = prefix[code];
  318.             }
  319.  
  320.             /* Push the last character on the stack, and set up the new
  321.              * prefix and suffix, and if the required slot number is greater
  322.              * than that allowed by the current bit size, increase the bit
  323.              * size.  (NOTE - If we are all full, we *don't* save the new
  324.              * suffix and prefix...  I'm not certain if this is correct...
  325.              * it might be more proper to overwrite the last code...
  326.              */
  327.  
  328.             *sp++ = code;
  329.             if (slot < top_slot)
  330.                 {
  331.                     suffix[slot] = fc = code;
  332.                     prefix[slot++] = oc;
  333.                     oc = c;
  334.                 }
  335.             if (slot >= top_slot)
  336.                 if (curr_size < 12)
  337.                 {
  338.                     top_slot <<= 1;
  339.                     ++curr_size;
  340.                 }
  341.  
  342.             /* Now that we've pushed the decoded string (in reverse order)
  343.              * onto the stack, lets pop it off and put it into our decode
  344.              * buffer...  And when the decode buffer is full, write another
  345.              * line...
  346.              */
  347.             while (sp > stack)
  348.             {
  349.                 *bufptr++ = *(--sp);
  350.                 if (--bufcnt == 0)
  351.                 {
  352.                     if ((ret = out_line(buf, linewidth)) < 0)
  353.                     {
  354.                         free(buf);
  355.                         return(ret);
  356.                     }
  357.                     bufptr = buf;
  358.                     bufcnt = linewidth;
  359.                 }
  360.             }
  361.         }
  362.     }
  363.     ret = 0;
  364.     if (bufcnt != linewidth)
  365.         ret = out_line(buf, (linewidth - bufcnt));
  366.     free(buf);
  367.     return(ret);
  368. }
  369.  
  370.